home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 July: Mac OS SDK / Dev.CD Jul 96 SDK / Dev.CD Jul 96 SDK1.toast / Development Kits (Disc 1) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc Source Code / Utilities / StrHshTb.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1996-04-22  |  19.8 KB  |  736 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        StrHshTb.cpp
  3.  
  4.     Contains:    Implementation for StringHashTable class.
  5.  
  6.     Owned by:    Nick Pilch
  7.  
  8.     Copyright:    © 1993 - 1995 by Apple Computer, Inc., all rights reserved.
  9.  
  10. */
  11.  
  12. /*
  13.     A simple hash table with chaining. Each hash table entry
  14.     is a HashEntryRec. Each HashEntryRec contains a pointer to start of a
  15.     linked list of EntryNodes. Each EntryNode contains the key, the length of
  16.     key, the value, the length of the value and at least
  17.     one link to another item in the list.
  18.     
  19.     The keys are stored as NULL terminated C-strings for debugging purposes
  20.     even though they may have imbedded NULLs.
  21. */
  22.  
  23. #ifndef _STRHSHTB_
  24. #include "StrHshTb.h"
  25. #endif
  26.  
  27. #ifndef __CTYPE__
  28. #include <ctype.h>
  29. #endif
  30.  
  31. #ifndef __LIMITS__
  32. #include <limits.h>
  33. #endif
  34.  
  35. #ifndef _EXCEPT_
  36. #include "Except.h"
  37. #endif
  38.  
  39. #ifndef __STRING__
  40. #include <string.h>
  41. #endif
  42.  
  43. #ifndef _ODNEW_
  44. #include "ODNew.h"
  45. #endif
  46.  
  47. #ifndef _UTILERRS_
  48. #include "UtilErrs.h"
  49. #endif
  50.  
  51. #pragma segment StringHashTable
  52.  
  53. //==============================================================================
  54. // Local Classes
  55. //==============================================================================
  56.  
  57. struct EntryNode
  58. {
  59.     ODUByte*    key;
  60.     ODULong    keySize;
  61.     ODPtr        value;
  62.     ODULong    valueLen;
  63.     EntryNode*    nextEntry; // == 0 means end of list.
  64. };
  65.  
  66. struct HashEntryRec
  67. {
  68.     EntryNode*    node;        //    pointer to first node
  69. };
  70.  
  71. #if 0
  72.     //OBSOLETE
  73.     struct LinkedNodesIterator
  74.     {
  75.         LinkedNodesIterator(StringHashTable* table, ODULong tableIndex)
  76.                             {fTableIndex = tableIndex; fTable = table;
  77.                                 fCurNode = (table->fTable + tableIndex)->node;}
  78.         EntryNode*    First() {return fCurNode;}
  79.         EntryNode*    Next() {return (fCurNode = fCurNode->nextEntry);}
  80.         ODBoolean    IsNotComplete() {return (fCurNode->nextEntry != 0);}
  81.       private:
  82.         StringHashTable*    fTable;
  83.         ODULong            fTableIndex;
  84.         EntryNode*            fCurNode;
  85.     };
  86. #endif // 0
  87.  
  88. struct LinkedNodesIterator
  89. {
  90.   public:
  91.     LinkedNodesIterator(StringHashTable* table, ODULong tableIndex);
  92.     EntryNode*    First();
  93.     EntryNode*    Next();
  94.     ODBoolean    IsNotComplete();
  95.   private:
  96.     StringHashTable*    fTable;
  97.     ODULong            fTableIndex;
  98.     EntryNode*            fCurNode;
  99.     ODBoolean            fDone;
  100. };
  101.  
  102. LinkedNodesIterator::LinkedNodesIterator(StringHashTable* table, ODULong tableIndex)
  103. {
  104.     fTableIndex = tableIndex;
  105.     fTable = table;
  106.     fCurNode = (table->GetTable() + tableIndex)->node;
  107.     fDone = kODFalse;
  108. }
  109.  
  110. EntryNode*    LinkedNodesIterator::First()
  111. {
  112.     return fCurNode;
  113. }
  114.  
  115. EntryNode*    LinkedNodesIterator::Next()
  116. {
  117.     if (fCurNode->nextEntry == kODNULL)
  118.     {
  119.         fDone = kODTrue;
  120.         return 0;
  121.     }
  122.     else
  123.         return (fCurNode = fCurNode->nextEntry);
  124. }
  125.  
  126. ODBoolean    LinkedNodesIterator::IsNotComplete()
  127. {
  128.     if (!fCurNode)
  129.         return kODFalse;
  130.     else
  131.         return !fDone;
  132. }
  133.  
  134.  
  135. //==============================================================================
  136. // StringHashTable
  137. //==============================================================================
  138.  
  139. //------------------------------------------------------------------------------
  140. // StringHashTable::StringHashTable
  141. //------------------------------------------------------------------------------
  142.  
  143. StringHashTable::StringHashTable(ODULong numEntries)
  144. {
  145.     if (numEntries == 0)
  146.         fNumSlots = 1;
  147.     else
  148.         fNumSlots = numEntries;
  149.     fHashFunc = StringHashTable::StdHash;
  150.     fNumEntries = 0;
  151.     fHeapID = kDefaultHeapID;
  152. }
  153.  
  154. //------------------------------------------------------------------------------
  155. // StringHashTable::Initialize
  156. //------------------------------------------------------------------------------
  157.  
  158. void StringHashTable::Initialize(ODMemoryHeapID heapID)
  159. {
  160.     ODULong    tableSize = fNumSlots * sizeof(HashEntryRec);
  161.  
  162.     fHeapID = heapID;
  163.     fTable = (HashEntryRec*)ODNewPtrClear(tableSize, fHeapID);
  164.     if (!fTable)
  165.         THROW(kODErrOutOfMemory);
  166. }
  167.  
  168. //------------------------------------------------------------------------------
  169. // StringHashTable::~StringHashTable
  170. //------------------------------------------------------------------------------
  171.  
  172. StringHashTable::~StringHashTable()
  173. {
  174.     // gotta be careful to delete a node only after we're done with it.
  175.     for (ODULong i = 0; i < fNumSlots; i++)
  176.     {
  177.         LinkedNodesIterator    iter(this, i);
  178.         EntryNode*            someNode;
  179.         EntryNode*            lastNode = 0; // first time through
  180.  
  181.         for (someNode = iter.First();
  182.                 iter.IsNotComplete();
  183.                 someNode = iter.Next())
  184.         {
  185.             if (lastNode)
  186.             {
  187.                 ODDisposePtr((Ptr)lastNode->key);
  188.                 ODDisposePtr((Ptr)lastNode);
  189.             }
  190.             lastNode = someNode;
  191.         }
  192.         if (lastNode)
  193.         {
  194.             ODDisposePtr((Ptr)lastNode->key);
  195.             ODDisposePtr((Ptr)lastNode);
  196.         }
  197.     }
  198.     ODDisposePtr((Ptr)fTable);
  199. }
  200.  
  201. //------------------------------------------------------------------------------
  202. // StringHashTable::Insert
  203. //
  204. //    Hash the key, Map the hash to the range of table index values, insert the
  205. //    hash into the linked list of EntryNodes at that table slot.
  206. //------------------------------------------------------------------------------
  207.  
  208. void StringHashTable::Insert(ODUByte* string, ODULong stringLength,
  209.                                         ODPtr value, ODULong valueLength)
  210. {
  211.     if (stringLength == 0)
  212.         THROW(kODErrInvalidKey);
  213.     if (value == (ODPtr)kODNULL)
  214.         THROW(kODErrIllegalNullInput);
  215.     ODULong tableIndex = this->HashAndMap(string, stringLength);
  216.     this->InsertAtIndex(tableIndex, string, stringLength, value, valueLength);
  217.     ++fNumEntries;
  218. }
  219.  
  220. //------------------------------------------------------------------------------
  221. // StringHashTable::InsertAtIndex
  222. //
  223. //    Insert a hash table node at the the specified index in the table.
  224. //------------------------------------------------------------------------------
  225.  
  226. void StringHashTable::InsertAtIndex(ODULong index, ODUByte* string,
  227.                                                 ODULong stringLength,
  228.                                                 ODPtr value,
  229.                                                 ODULong valueLength)
  230. {
  231.     HashEntryRec*    entry = fTable + index;
  232.     
  233.     // No nodes at this table entry? Stick in the first one.
  234.     if (entry->node == kODNULL)
  235.         entry->node = this->MakeNewNode(string, stringLength, value,
  236.                                         valueLength);
  237.     // Else, need to follow chain to end checking for duplicate keys
  238.     else
  239.     {
  240.         LinkedNodesIterator    iter(this, index);
  241.         EntryNode*            someNode;
  242.         EntryNode*            lastNode;
  243.         ODBoolean            replaceOne = kODFalse;
  244.         ODBoolean            alreadyHadKey = kODFalse;
  245.  
  246.         // Iterate to the end of the list or until we find the key
  247.         for (someNode = iter.First();
  248.                 iter.IsNotComplete();
  249.                 lastNode = someNode, someNode = iter.Next())
  250.         {
  251.             if ((someNode->keySize == stringLength)
  252.                 && (!memcmp((const char*)someNode->key, (const char*)string,
  253.                             (size_t)stringLength)))
  254.             {
  255.                 someNode->value = value;
  256.                 someNode->valueLen = valueLength;
  257.                 alreadyHadKey = kODTrue;
  258.                 break;
  259.             }
  260.         }
  261.         if (!alreadyHadKey)
  262.             // If we got here, we have to create a new node.
  263.             lastNode->nextEntry = MakeNewNode(string, stringLength, value,
  264.                                                 valueLength);
  265.     }
  266. }
  267.  
  268. //------------------------------------------------------------------------------
  269. // StringHashTable::MakeStringFromBytes
  270. //
  271. //    Create a new NULL-terminated C-string from a stream of bytes.
  272. //------------------------------------------------------------------------------
  273.  
  274. ODUByte* StringHashTable::MakeStringFromBytes(ODUByte* string,
  275.                                                     ODULong stringLength)
  276. {
  277.     ODUByte* newString = (ODUByte*)ODNewPtr(stringLength + 1, fHeapID);
  278.     if (!newString)
  279.         THROW(kODErrOutOfMemory);
  280.     ODBlockMove(string, newString, stringLength);
  281.     newString[stringLength] = 0;
  282.     return newString;
  283. }
  284.  
  285. //------------------------------------------------------------------------------
  286. // StringHashTable::MakeNewNode
  287. //
  288. //    Allocate and intialize a new entry node.
  289. //------------------------------------------------------------------------------
  290.  
  291. EntryNode* StringHashTable::MakeNewNode(ODUByte* string,
  292.                                             ODULong stringLength, ODPtr value,
  293.                                             ODULong valueLength)
  294. {
  295.     EntryNode* newNode = (EntryNode*)ODNewPtr(sizeof(EntryNode), fHeapID);
  296.  
  297.     // Convert strings to C-strings and copy
  298.     ODUByte* newString = this->MakeStringFromBytes(string, stringLength);
  299.     
  300.     newNode->key = newString;
  301.     newNode->keySize = stringLength;
  302.     newNode->nextEntry = kODNULL;
  303.     newNode->value = value;
  304.     newNode->valueLen = valueLength;
  305.     
  306.     return newNode;
  307. }
  308.  
  309. //------------------------------------------------------------------------------
  310. // StringHashTable::Remove
  311. //
  312. //    Hash the key, Map the hash to the range of table index values, search the
  313. //    the linked list of EntryNodes for the key, remove the EntryNode in which
  314. //    the key was found.
  315. //------------------------------------------------------------------------------
  316.  
  317. void StringHashTable::Remove(ODUByte* string, ODULong stringLength)
  318. {
  319.     if (stringLength == 0)
  320.         THROW(kODErrInvalidKey);
  321.     ODULong tableIndex = this->HashAndMap(string, stringLength);
  322.     this->RemoveAtIndex(tableIndex, string, stringLength);
  323.     --fNumEntries;
  324. }
  325.  
  326. //------------------------------------------------------------------------------
  327. // StringHashTable::RemoveAtIndex
  328. //
  329. //    Remove a hash table node at the the specified index in the table.
  330. //------------------------------------------------------------------------------
  331.  
  332. void StringHashTable::RemoveAtIndex(ODULong index, ODUByte* string,
  333.                                                 ODULong stringLength)
  334. {
  335.     HashEntryRec*    entry = fTable + index;
  336.     
  337.     if (entry->node != kODNULL)
  338.     {
  339.         LinkedNodesIterator    iter(this, index);
  340.         EntryNode*            someNode;
  341.         EntryNode*            prevNode = 0; // start of chain
  342.  
  343.         for (someNode = iter.First();
  344.                 iter.IsNotComplete();
  345.                 someNode = iter.Next())
  346.         {
  347.             // look for a match
  348.             if ((someNode->keySize == stringLength)
  349.                 && (!memcmp((const char*)someNode->key, (const char*)string,
  350.                             (size_t)stringLength)))
  351.             {
  352.                 // Special case first node
  353.                 if (prevNode == 0)
  354.                     entry->node = someNode->nextEntry;
  355.                 else
  356.                     prevNode->nextEntry = someNode->nextEntry;
  357.  
  358.                 // Must dispose someNode->key first or else we'll lose its
  359.                 //    reference after disposing the someNode.
  360.                 ODDisposePtr((Ptr)someNode->key);
  361.                 ODDisposePtr((Ptr)someNode);
  362.                 break;
  363.             }
  364.             prevNode = someNode;
  365.         }
  366.     }
  367. }
  368.  
  369. //------------------------------------------------------------------------------
  370. // StringHashTable::Find
  371. //
  372. //    Hash the key, Map the hash to the range of table index values, search the
  373. //    the linked list of EntryNodes for the key. Signal error if not found.
  374. //------------------------------------------------------------------------------
  375.  
  376. ODBoolean StringHashTable::Find(ODUByte* string, ODULong stringLength,
  377.                                     ODPtr* value, ODULong* valueLength)
  378. {
  379.     ODULong        tableIndex = this->HashAndMap(string, stringLength);
  380.     HashEntryRec*    entry = fTable + tableIndex;
  381.     ODBoolean        result = kODFalse;
  382.     
  383.     if (stringLength == 0)
  384.         THROW(kODErrInvalidKey);
  385.  
  386.     if (entry->node != kODNULL)
  387.     {
  388.         LinkedNodesIterator    iter(this, tableIndex);
  389.         EntryNode*            someNode;
  390.  
  391.         for (someNode = iter.First();
  392.                 iter.IsNotComplete();
  393.                 someNode = iter.Next())
  394.         {
  395.             // match
  396.             if ((someNode->keySize == stringLength)
  397.                 && (!memcmp((const char*)someNode->key, (const char*)string,
  398.                             (size_t)stringLength)))
  399.             {
  400.                 *value = someNode->value;
  401.                 *valueLength = someNode->valueLen;
  402.                 result = kODTrue;
  403.                 break;
  404.             }
  405.         }
  406.     }
  407.  
  408.     return result;
  409. }
  410.  
  411. //------------------------------------------------------------------------------
  412. // StringHashTable::Exists
  413. //
  414. //    Hash the key, Map the hash to the range of table index values, search the
  415. //    the linked list of EntryNodes for the key. Signal error if not found.
  416. //------------------------------------------------------------------------------
  417.  
  418. ODBoolean StringHashTable::Exists(ODUByte* string, ODULong stringLength)
  419. {
  420.     ODULong        tableIndex = this->HashAndMap(string, stringLength);
  421.     HashEntryRec*    entry = fTable + tableIndex;
  422.     ODBoolean        result = kODFalse;
  423.     
  424.     //if (stringLength == 0)
  425.         //THROW(kODErrInvalidKey);
  426.  
  427.     if (stringLength != 0)
  428.     {
  429.         if (entry->node != kODNULL)
  430.         {
  431.             LinkedNodesIterator    iter(this, tableIndex);
  432.             EntryNode*            someNode;
  433.     
  434.             for (someNode = iter.First();
  435.                     iter.IsNotComplete();
  436.                     someNode = iter.Next())
  437.             {
  438.                 // match
  439.                 if ((someNode->keySize == stringLength)
  440.                     && (!memcmp((const char*)someNode->key, (const char*)string,
  441.                                 (size_t)stringLength)))
  442.                 {
  443.                     result = kODTrue;
  444.                     break;
  445.                 }
  446.             }
  447.         }
  448.     }
  449.  
  450.     return result;
  451. }
  452.  
  453. //------------------------------------------------------------------------------
  454. // StringHashTable::GetNumEntries
  455. //------------------------------------------------------------------------------
  456.  
  457. ODULong StringHashTable::GetNumEntries()
  458. {
  459.     return fNumEntries;
  460. }
  461.  
  462. //------------------------------------------------------------------------------
  463. // StringHashTable::StdHash
  464. //
  465. //    Adds all the characters in the string and returns the smallest and largest
  466. //    numbers that they could add up to in hashValueLowerBounds and
  467. //    hashValueUpperBounds.
  468. //------------------------------------------------------------------------------
  469.  
  470. ODULong StringHashTable::StdHash(ODUByte* string,
  471.                                             ODULong stringLength,
  472.                                             ODULong& hashValueLowerBounds,
  473.                                             ODULong& hashValueUpperBounds)
  474. {
  475.     ODULong    result = 0;
  476.  
  477.     for (ODULong i = 0; i < stringLength; i++)
  478.     {
  479.         result += *(string + i);
  480.     }
  481.     hashValueLowerBounds = 0;
  482.     hashValueUpperBounds = 255 * stringLength;
  483.     return result;
  484. }
  485.  
  486. //------------------------------------------------------------------------------
  487. // StringHashTable::MapToTableIndex
  488. //
  489. //    Map hash value in its range to the range 0..(fNumSlots - 1).
  490. //------------------------------------------------------------------------------
  491.  
  492. ODULong StringHashTable::MapToTableIndex(ODULong hash,
  493.                                                 ODULong hashValueLowerBounds,
  494.                                                 ODULong hashValueUpperBounds)
  495. {
  496.     if (hashValueLowerBounds >= hashValueUpperBounds)
  497.         return 0;
  498.     else
  499.     {
  500.         double index = (double)(hash - hashValueLowerBounds)
  501.             / (double)(hashValueUpperBounds - hashValueLowerBounds)
  502.             * (double)(fNumSlots - 1);
  503.         double indexToRound = index + .5;
  504.         return (ODULong)indexToRound;
  505.     }
  506. }
  507.  
  508. //------------------------------------------------------------------------------
  509. // StringHashTable::HashAndMap
  510. //
  511. //    Utility function.
  512. //------------------------------------------------------------------------------
  513.  
  514. ODULong StringHashTable::HashAndMap(ODUByte* string, ODULong stringLength)
  515. {
  516.     ODULong    hashUpperBounds, hashLowerBounds;
  517.  
  518.     ODULong hash = fHashFunc(string, stringLength, hashLowerBounds,
  519.                                 hashUpperBounds);
  520.     return this->MapToTableIndex(hash, hashLowerBounds, hashUpperBounds);
  521. }
  522.  
  523. //------------------------------------------------------------------------------
  524. // StringHashTable::PrintTable
  525. //
  526. //    Testing / Debugging function.
  527. //------------------------------------------------------------------------------
  528.  
  529. #include <stdio.h>
  530.  
  531. void StringHashTable::PrintTable(FILE* outfile)
  532. {
  533.     StringHashTableIterator    iter(this);
  534.     ODUByte*                    string;
  535.     ODULong                    len;
  536.     ODPtr                        value;
  537.     ODULong                    valueLen;
  538.  
  539.     fprintf(outfile, "The table contains this:\n");
  540.  
  541.     for (iter.First(&string, &len, &value, &valueLen);
  542.             iter.IsNotComplete();
  543.             iter.Next(&string, &len, &value, &valueLen))
  544.     {    
  545.         fprintf(outfile, "%s, %d%d\n", string, value, valueLen);
  546.     }
  547.  
  548.     fprintf(outfile, "\n");
  549. }
  550.  
  551. //------------------------------------------------------------------------------
  552. // StringHashTable::PrintDistribution
  553. //
  554. //    Testing / Debugging function.
  555. //------------------------------------------------------------------------------
  556.  
  557. void StringHashTable::PrintDistribution(FILE* outfile)
  558. {
  559.     fprintf(outfile, "The table looks like this:\n");
  560.  
  561.     for (ODULong i = 0; i < fNumSlots; i++)
  562.     {
  563.         fprintf(outfile, "Slot %d:\n", i);
  564.  
  565.         LinkedNodesIterator    iter(this, i);
  566.         EntryNode*            someNode;
  567.  
  568.         for (someNode = iter.First();
  569.                 iter.IsNotComplete();
  570.                 someNode = iter.Next())
  571.         {
  572.             fprintf(outfile, "\t%s\n", someNode->key);
  573.         }
  574.     }
  575.  
  576.     fprintf(outfile, "\n");
  577. }
  578.  
  579. //------------------------------------------------------------------------------
  580. // StringHashTable::GetHashFunc
  581. //------------------------------------------------------------------------------
  582.  
  583. StringHashTableFunc StringHashTable::GetHashFunc()
  584. {
  585.     return fHashFunc;
  586. }
  587.  
  588. //------------------------------------------------------------------------------
  589. // StringHashTable::SetHashFunc
  590. //------------------------------------------------------------------------------
  591.  
  592. void StringHashTable::SetHashFunc(StringHashTableFunc func)
  593. {
  594.     fHashFunc = func;
  595. }
  596.  
  597. //------------------------------------------------------------------------------
  598. // StringHashTable::GetNumSlots
  599. //
  600. //    For friends.
  601. //------------------------------------------------------------------------------
  602.  
  603. ODULong StringHashTable::GetNumSlots()
  604. {
  605.     return fNumSlots;
  606. }
  607.  
  608. //------------------------------------------------------------------------------
  609. // StringHashTable::GetTable
  610. //
  611. //    For friends.
  612. //------------------------------------------------------------------------------
  613.  
  614. HashEntryRec* StringHashTable::GetTable()
  615. {
  616.     return fTable;
  617. }
  618.  
  619. //==============================================================================
  620. // StringHashTableIterator
  621. //==============================================================================
  622.  
  623. //------------------------------------------------------------------------------
  624. // StringHashTableIterator::StringHashTableIterator
  625. //------------------------------------------------------------------------------
  626.  
  627. StringHashTableIterator::StringHashTableIterator(StringHashTable* tb)
  628. {
  629.     fTable = tb;
  630.     fTableIndex = 0;
  631.     fCurNode = kODNULL;
  632.     fDone = kODFalse;
  633. }
  634.  
  635. //------------------------------------------------------------------------------
  636. // StringHashTableIterator::~StringHashTableIterator
  637. //------------------------------------------------------------------------------
  638.  
  639. StringHashTableIterator::~StringHashTableIterator()
  640. {
  641. }
  642.  
  643. //------------------------------------------------------------------------------
  644. // StringHashTableIterator::First
  645. //
  646. //    Use GetNext to find first. Set flag if we don't find an entry.
  647. //------------------------------------------------------------------------------
  648.  
  649. void StringHashTableIterator::First(ODUByte** string, ODULong* len,
  650.                                             ODPtr* value,
  651.                                             ODULong* valueLength)
  652. {
  653.     if (!this->GetNext(string, len, value, valueLength))
  654.     {
  655. //        *len  = 0;
  656. //        *string = (ODUByte*)kODNULL;
  657.         fDone = kODTrue;
  658.     }
  659. }
  660.  
  661. //------------------------------------------------------------------------------
  662. // StringHashTableIterator::Next
  663. //
  664. //    Use GetNext. Set flag if we don't find an entry.
  665. //------------------------------------------------------------------------------
  666.  
  667. void StringHashTableIterator::Next(ODUByte** string, ODULong* len,
  668.                                             ODPtr* value,
  669.                                             ODULong* valueLength)
  670. {
  671.     if (!this->GetNext(string, len, value, valueLength))
  672.     {
  673. //        *len  = 0;
  674. //        *string = (ODUByte*)kODNULL;
  675.         fDone = kODTrue;
  676.     }
  677. }
  678.  
  679. //------------------------------------------------------------------------------
  680. // StringHashTableIterator::IsNotComplete
  681. //
  682. //    Return value of previously set flag.
  683. //------------------------------------------------------------------------------
  684.  
  685. ODBoolean StringHashTableIterator::IsNotComplete()
  686. {
  687.     return !fDone;
  688. }
  689.  
  690. //------------------------------------------------------------------------------
  691. // StringHashTableIterator::GetNext
  692. //
  693. // kODTrue is returned if an entry was found, kODFalse otherwise. The
  694. //    values pointed to by the parameters are undefined if kODFalse is
  695. //    returned.
  696. //    We can record the index of the last hash bucket we were looking in, but we
  697. //    can't record the index into the linked list at that bucket. So we keep a
  698. //    pointer to the last node found and look for it the next time we iterate
  699. //    through that list.
  700. //------------------------------------------------------------------------------
  701.  
  702. ODBoolean StringHashTableIterator::GetNext(ODUByte** string, ODULong* len,
  703.                                                 ODPtr* value,
  704.                                                 ODULong* valueLength)
  705. {
  706.     for (ODULong i = fTableIndex; i < fTable->GetNumSlots(); i++)
  707.     {
  708.         LinkedNodesIterator    iter(fTable, i);
  709.         EntryNode*            someNode;
  710.         ODBoolean            pastLastNode = fCurNode ? kODFalse : kODTrue;
  711.  
  712.         for (someNode = iter.First();
  713.                 iter.IsNotComplete();
  714.                 someNode = iter.Next())
  715.         {
  716.             if ((i == fTableIndex) && (someNode == fCurNode))
  717.             {
  718.                 pastLastNode = kODTrue;
  719.                 continue;
  720.             }
  721.             if (pastLastNode || (i != fTableIndex))
  722.             {
  723.                 fTableIndex = i;
  724.                 fCurNode = someNode;
  725.                 *string = someNode->key;
  726.                 *len = someNode->keySize;
  727.                 *value = someNode->value;
  728.                 *valueLength = someNode->valueLen;
  729.                 return kODTrue;
  730.             }
  731.         }
  732.     }
  733.     return kODFalse;
  734. }
  735.  
  736.